public class Sort {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 将给定数组排序，升序
     * 
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort(int[] arr) {
        // write code here
        // 选择排序,超时 O(n^2)
        // int len = arr.length;
        // for (int i = 0; i < len - 1; ++i) {
        // for (int j = i + 1; j < len; ++j) {
        // if (arr[j] < arr[i]) {
        // int temp = arr[i];
        // arr[i] = arr[j];
        // arr[j] = temp;
        // }
        // }
        // }
        // return arr;
        // // 冒泡排序+优化（判断是否初始便有序）,逐个交换把大的沉底（或小的沉底）超时 O(n^2)
        // int len = arr.length;
        // for (int i = 0; i < len - 1; ++i) {
        // boolean isSort = true;
        // for (int j = 0; j < len - 1 - i; ++j) {
        // if (arr[j] > arr[j + 1]) {
        // int temp = arr[j];
        // arr[j] = arr[j + 1];
        // arr[j + 1] = temp;
        // isSort = false; // 标记该数组是否已经有序
        // }
        // }
        // if (isSort)
        // break;
        // }
        // return arr;
        // // 插入排序，勉强通过 O(n^2)
        // int n = arr.length;
        // for (int i = 1; i < n; ++i) {
        // int value = arr[i];
        // int j = 0;// 插入的位置
        // for (j = i - 1; j >= 0; j--) {
        // if (arr[j] > value) {
        // arr[j + 1] = arr[j];// 移动数据
        // } else {
        // break;
        // }
        // }
        // arr[j + 1] = value; // 插入数据
        // }
        // return arr;
        // // 希尔排序 O(n^1.3)
        // int length = arr.length;
        // // 区间
        // int gap = 1;
        // while (gap < length) {
        // gap = gap * 3 + 1;
        // }
        // while (gap > 0) {
        // for (int i = gap; i < length; i++) {
        // int tmp = arr[i];
        // int j = i - gap;
        // // 跨区间排序
        // while (j >= 0 && arr[j] > tmp) {
        // arr[j + gap] = arr[j];
        // j -= gap;
        // }
        // arr[j + gap] = tmp;
        // }
        // gap = gap / 3;
        // }
        // return arr;
        // 快排 双边扫描 O(nlogn)
        sort(arr, 0, arr.length - 1);
        return arr;
    }

    private void sort(int[] arr, int startIndex, int endIndex) {
        if (endIndex <= startIndex) {
            return;
        }
        // 切分
        int pivotIndex = partition(arr, startIndex, endIndex);
        sort(arr, startIndex, pivotIndex - 1);
        sort(arr, pivotIndex + 1, endIndex);
    }

    private int partition(int[] arr, int startIndex, int endIndex) {
        int left = startIndex;
        int right = endIndex;
        int pivot = arr[startIndex];// 取第一个元素为基准值

        while (true) {
            // 从左往右扫描
            while (arr[left] <= pivot) {
                left++;
                if (left == right) {
                    break;
                }
            }

            // 从右往左扫描
            while (pivot < arr[right]) {
                right--;
                if (left == right) {
                    break;
                }
            }

            // 左右指针相遇
            if (left >= right) {
                break;
            }

            // 交换左右数据
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }

        // 将基准值插入序列
        int temp = arr[startIndex];
        arr[startIndex] = arr[right];
        arr[right] = temp;
        return right;
    }

    public void quickSort(int array[], int low, int high) {// 传入low=0，high=array.length-1;
        int pivot, p_pos, i, t;// pivot->位索引;p_pos->轴值。
        if (low < high) {
            p_pos = low;
            pivot = array[p_pos];
            for (i = low + 1; i <= high; i++)
                if (array[i] < pivot) {
                    p_pos++;
                    t = array[p_pos];
                    array[p_pos] = array[i];
                    array[i] = t;
                }
            t = array[low];
            array[low] = array[p_pos];
            array[p_pos] = t;
            // 分而治之
            quickSort(array, low, p_pos - 1);// 排序左半部分
            quickSort(array, p_pos + 1, high);// 排序右半部分
        }
    }
}
